% Author: Yang Ge, 
% standard genetic algorithm

% selection also known as reproduction, according to the fitness of each
% seed, choose the high fitness seed to the next turn.
% parameters:
% params.seeds = 50
% params.dimension = 5
% params.digits = 10
% params.crossover_rate = 
% params.mutation_rate =
% params.iterations = 200
% params.upper_bound = 20
% params.lower_bound = -20
% params.func = 
function result = GA(params)
global digits;

seeds = params.seeds;
dimension = params.dimension;
digits = params.digits;
crossover_rate = params.crossover_rate;
mutation_rate = params.mutation_rate;

upper_bound = params.upper_bound;
lower_bound = params.lower_bound;
func = params.func;

seeds_fitness = zeros(1, seeds);
next_seeds_matrix = zeros(seeds, dimension);
next_seeds_bin_matrix = zeros(seeds, dimension * digits);
% randomly initilize the seeds matrix
seeds_matrix = rand(seeds, dimension) * ...
                                    (upper_bound - lower_bound) + lower_bound;
seeds_bin_matrix = zeros(seeds, dimension * digits);

for seed = 1 : seeds
    % calculate the fitness of the initial generation
    seeds_fitness(seed) = func(seeds_matrix(seed,:));
end
result(1) = min(seeds_fitness);

% iteration
for gen = 2 :params.iterations
    for seed = 1:seeds
        % encoding to the binary digits
        seeds_bin_matrix(seed,:) = dec_to_binary_vector(seeds_matrix(seed,:));
    end
    % select good fitness seeds for the next generation
    total_fitness = sum(seeds_fitness);
    seeds_probability = seeds_fitness / total_fitness;
    seeds_accumulate_probability = cumsum(seeds_probability, 2);
    % roulet select
    for i = 1:seeds
        random_spinning = rand;
        selected_index = 1;
        while random_spinning > seeds_accumulate_probability(selected_index) ...
                && selected_index < seeds
            selected_index = selected_index + 1;
        end
        next_seeds_matrix(i,:) = seeds_matrix(selected_index,:);
        next_seeds_bin_matrix(i,:) = seeds_bin_matrix(selected_index,:);
    end

    % crossover operation based on the crossover rate
    % select a pair of seeds in sequence order
    for cr = 1:2:seeds
        probability = rand;
        if probability < crossover_rate
            % randomly generate a seed, just for deciding which gene should be switch 
            temp_seed = randi([0,1], 1, dimension * digits);
            for j = 1 : length(temp_seed)
                if temp_seed(j) == 1
                    % swap seeds gene at j index
                    temp = next_seeds_bin_matrix(cr,j);
                    next_seeds_bin_matrix(cr, j) = next_seeds_bin_matrix(cr+1, j);
                    next_seeds_bin_matrix(cr+1, j) = temp;
                end
            end
        end
    end

    % mutation operation according to the mutation rate 
    for mu = 1 : round(mutation_rate * seeds)
        for i = 1 : round(mutation_rate * digits)
            next_seeds_bin_matrix(mu, i) = ~next_seeds_bin_matrix(mu, i);
        end
    end
    
    for seed = 1 : seeds
        next_seeds_matrix = binary_to_dec(next_seeds_bin_matrix(seed,:));
    end
    % next generation matrix  
    seeds_matrix = next_seeds_matrix;
    
    % calculate fitness of new generation
    for seed = 1 : seeds
        seeds_fitness(seed) = func(seeds_matrix(seed,:));
    end
    result(gen) = min(seeds_fitness);
end
end

